<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            时间：O(N^2)
            空间：O(N)
        */
        function TreeNode(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        var constructMaximumBinaryTree = function (nums) {
            // 退出条件
            if (nums.length === 0) {
                return null
            }

            // 只有一个元素
            if (nums.length === 1) {
                return new TreeNode(nums[0])
            }

            // 找到里面的最大值
            let max = 0
            let deli;
            for (let i = 0; i < nums.length; i++) {
                if (nums[i] > max) {
                    max = nums[i]
                    deli = i
                }
            }
            // 头结点是最大值
            let root = new TreeNode(nums[deli])

            /* 
                这题比上面三题几乎一样，甚至更加简单
            */
            const leftNums = nums.slice(0, deli)
            const rightNums = nums.slice(deli + 1)

            root.left = constructMaximumBinaryTree(leftNums)
            root.right = constructMaximumBinaryTree(rightNums)
            // 返回内容
            return root
        };
        console.log(constructFromPrePost([1,2,4,5,3,6,7], [4,5,2,6,7,3,1]));
        // console.log(constructFromPrePost([2, 3, 6, 8, 9, 5], [6, 3, 8, 9, 2, 5]));
    </script>
</body>

</html>